class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        begin = 1
        end = n
        stride = 1
        while n>1:
            # from left to right
            begin+=stride
            if n%2==1: end-=stride
            stride *= 2
            n//=2
            if n==1: break
            # from right to left
            end-=stride
            if n%2==1: begin+=stride
            stride*=2
            n//=2
        return begin

print(Solution().lastRemaining(9))